/*
 * @Author: your name
 * @Date: 2021-04-07 15:02:02
 * @LastEditTime: 2021-04-07 15:56:35
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \git\Javascript-github\YiHzo-Javascript-master\Javascript\数据结构与算法\队列\3.双队列.js
 */
/**
 * 双队列结构:
 * 能同时头部和尾部进行添加，删除操作
 */
class Deque {
  constructor() {
    this.count = 0; // 队列大小
    this.lowestCount = 0; // 队列第一位
    this.items = {};
  }
  /**
   * 队列大小
   */
  size() {
    return this.count - this.lowestCount;
  }
  /**
   * 队列是否为空
   */
  isEmpty() {
    return this.size() === 0;
  }
  /**
   * 清除队列
   */
  clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  /**
   * 队列转字符串
   */
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let strObj = this.items[this.lowestCount];
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      strObj = `${strObj},${this.items[i]}`;
    }
    return strObj;
  }
  /**
   * 向队列头部添加元素
   */
  addFront(element) {
    // 1. 如果队列为空
    // 2. lowestCount > 0
    // 3. lowestCount === 0
    if (this.isEmpty()) {
      this.addBack(element);
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      // 将队列往后挪
      for (let i = 0; i < this.count; i++) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = element;
    }
  }
  /**
   * 向队列尾部添加元素
   */
  addBack(element) {
    this.items[this.count] = element;
    this.count++;
  }
  /**
   * 移除头部元素
   */
  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }
  /**
   * 移除尾部元素
   */
  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }
  /**
   * 查询头部元素
   */
  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }
  /**
   * 查询尾部元素
   */
  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }
}

/********************************************************************/

const deque = new Deque();
console.log(deque.isEmpty()); // true
deque.addBack("AAA");
deque.addBack("BBB");
console.log(deque.toString()); // AAA,BBB
deque.addBack("CCC");
console.log(deque.toString()); // AAA,BBB,CCC
console.log(deque.size()); // 3
deque.removeFront();
console.log(deque.toString()); // BBB,CCC
deque.removeBack();
console.log(deque.toString()); // BBB
deque.addFront("DDD");
console.log(deque.peekFront()); // DDD
console.log(deque.peekBack()); // BBB
console.log(deque.toString()); // DDD,BBB
